package com.mid;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 多数元素 II   摩尔投票,  给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
 * @date 2022/7/24 16:47
 */
public class Demo229 {

    public static void main(String[] args) {

    }

    public List<Integer> majorityElement(int[] nums) {
        List<Integer> list=new ArrayList<>();
        if(nums.length<=0){
            return new ArrayList<>();
        }
        if(nums.length==1){
            list.add(nums[0]);
            return list;
        }
        int count1=0;
        int count2=0;
        int moer1=nums[0];
        int moer2=nums[0];
        for (int num : nums) {
            if(num==moer1){
                count1++;

            }
            else if(num==moer2){
                count2++;
            }else if(count1==0){
                moer1=num;
                count1++;
            }else if(count2==0){
                moer2=num;
                count2++;
            }else {
                count1--;
                count2--;
            }
        }
        count1=0;
        count2=0;
        for (int num : nums){
            if (moer1==num) {
                count1++;
            }
            if (moer2==num) {
                count2++;
            }
        }
        if(count1>nums.length/3){
            list.add(moer1);
        }
        if(count2>nums.length/3&&moer1!=moer2){
            list.add(moer2);
        }
       return list;
    }
}
